// https://www.lintcode.com/problem/palindrome-partitioning-ii/

public class Solution {
    /**
     * @param s: A string
     * @return: An integer
     */
    public int minCut(String s) {
        // write your code here
        /*
        这里多加一个虚拟元素，表示第i之后的元素最多可以分割几次。
        statuses则是空间换时间，记录s[i:j + 1]是否回文。
        */
        int[] ret = new int[s.length() + 1];
        for (int i = 0; i <= s.length(); ++i) {
            ret[i] = s.length() - i;
        }
        boolean[][] statuses = new boolean[s.length()][s.length()]; // s[i:j]是否为回文
        for (int i = 0; i < s.length(); ++i) {
            Arrays.fill(statuses[i], false);
        }
        for (int i = s.length() - 1; i >= 0; --i) {
            for (int j = i; j < s.length(); ++j) {
                /*
                如果以下条件满足，则s[i:j + 1]为回文
                1. s[i] == s[j]
                2. ij相邻或者s[i + 1:j]是回文
                */
                Character ci = s.charAt(i);
                Character cj = s.charAt(j);
                if ((ci == cj) && (((j - 1) <= i) || (statuses[i + 1][j - 1] == true))) {
                    statuses[i][j] = true;
                    /*
                    因为s[i:j + 1是回文]，所以在j这里切一刀可能会是更好的选择。
                    在j这里切下后，因为s[i:j + 1]是回文，所以分割次数是cuts[j + 1] + 1，
                    1是在j这里做的一次切割。
                    */
                    ret[i] = Math.min(ret[i], ret[j + 1] + 1);
                }
            }
        }
        return ret[0] -1; // 因为第0个是虚拟元素，所以要扣除一次。
    }
}